#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution01 {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int len = points.size();
        // if (len == 1) return len;
        // 判断相交区间的数量
        sort(points.begin(), points.end());
        int arrownum = 0;
        int right = points[0][1];

        for (int i = 1; i < len; i++) {
            int a = points[i][0], b = points[i][1];
            if (right >= a) {
                right = min(b, right);
            } else {
                arrownum++;
                right = b;
            }
        }
        return arrownum + 1;
    }
};

class Solution02 {
    unordered_map<long long, int> hash;
public:
    int integerReplacement(long long n) {
        // return dfs(n);
        int ret = 0;
        while (n != 1) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                if (n == 3) {
                    ret += 2;
                    break;
                }
                if ((n >> 1) & 1) n += 1;
                else n -= 1;
            }
            ret++;
        }
        return ret;
    }

    int dfs(long long num) {
        if (hash.count(num)) return hash[num];
        if (num == 1) return 0;
        if (num % 2 == 0) {
            int ret = 1 + dfs(num / 2);
            hash[num] = ret;
            return ret;
        } else {
            // if (num == INT_MAX) return dfs(num - 1);
            
            int left = dfs(num - 1) + 1;
            
            int right = dfs(num + 1) + 1;
            int ret = min(left, right);
            hash[num] = ret;
            return ret;
        }
    }

};

class Solution03 {
    bool isLager(const vector<int>& left, const vector<int>& right) {
        return (left[0] > right[0] && left[1] > right[1]);
    }

    // bool canEnter(const vector<int>& left, const vector<int>& right) {

    // }
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        // sort(envelopes.begin(), envelopes.end());
        // int len = envelopes.size();
        // vector<int> dp(len, 1);
        // int ret = 1;
        // for (int i = 1; i < len; i++) {
        //     for (int j = 0; j <= i - 1; j++) {
        //         if (envelopes[i][0] > envelopes[j][0]&& envelopes[i][1] > envelopes[j][1]) 
        //             dp[i] = max(dp[i], dp[j] + 1);
        //     }
        //     ret = max(ret, dp[i]);
        // }
        
        // return ret;
        
        // sort(envelopes.begin(), envelopes.end(), [&](vector<int>& x, vector<int>& y) {
        //     return (x[0] < y[0] || (x[0] == y[0] && x[1] > y[1]));
        // });

        // for (auto& e : envelopes) {
        //     cout << e[1] << " ";
        // }
        // vector<vector<int>> minenvelope;
        // // 使用二分 + 贪心
        // int index = 0, len = envelopes.size();
        // while (index < len) {
        //     if (minenvelope.empty() || isLager(envelopes[index], minenvelope.back())) {
        //         minenvelope.push_back(envelopes[index]);
        //     } else {
        //         // 找到插入位置
        //         int left = 0, right = minenvelope.size() - 1;
        //         while (left < right) {
        //             int mid = left + (right - left) / 2;
        //             if (isLager(envelopes[index], minenvelope[mid])) right = mid - 1;
        //             else left = mid + 1;
        //         }
        //         // if (isLager(minenvelope[left], envelopes[index]))
        //         minenvelope[left] = envelopes[index];
        //     }
        //     index++;
        // }
        // return minenvelope.size();

        sort(envelopes.begin(), envelopes.end(), [&](vector<int>& x, vector<int>& y) {
            return (x[0] < y[0] || (x[0] == y[0] && x[1] > y[1]));
        });

        vector<int> minenvelope;
        // 使用二分 + 贪心
        int index = 0, len = envelopes.size();
        while (index < len) {
            if (minenvelope.empty() || envelopes[index][1] > minenvelope.back()) {
                minenvelope.push_back(envelopes[index][1]);
            } else {
                // 找到插入位置
                int left = 0, right = minenvelope.size() - 1;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (envelopes[index][1] <=  minenvelope[mid]) right = mid;
                    else left = mid + 1;
                }
                // if (isLager(minenvelope[left], envelopes[index]))
                minenvelope[left] = envelopes[index][1];
            }
            index++;
        }
        return minenvelope.size();
    }
};

class Solution04 {
public:
    int pileBox(vector<vector<int>>& box) {
        sort(box.begin(), box.end());
        int len = box.size();
        vector<int> height;
        for (auto& e : box)
            height.push_back(e[2]);
        int ret = height[0];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2]) {
                    height[i] = max(height[i], height[j] + box[i][2]);
                }
            }
            ret = max(ret, height[i]);
        }
        return ret;
    }
};

class Solution05 {
public:
    int maxSumDivThree(vector<int>& nums) {
        //     priority_queue<int, vector<int>, greater<int>> Mone, Mtwo;
        //     // 找到最小的
        //     int sum = 0;
        //     for (auto& e : nums) {
        //         if (e % 3 == 1) {
        //             Mone.push(e);
        //             if (Mone.size() > 2)
        //                 Mone.pop();
        //         }
        //         if (e % 3 == 2) {
        //             Mtwo.push(e);
        //             if (Mtwo.size() > 2)
        //                 Mtwo.pop();
        //         }
        //         sum += e;
        //     }

        //     cout << "one size: " << Mone.size() << " sum: " << sum << endl;;
        //     while (sum % 3 != 0) {
        //         if (sum % 3 == 1) {
        //             // 拿出最小的1，以及两个2
        //             int one = Mone.top();
        //             if (Mtwo.size() == 2) {
        //                 int two1 = Mtwo.top();
        //                 Mtwo.pop();
        //                 int two2 = Mtwo.top();
        //                 sum = max(sum - one, sum - two1 - two2);
        //             } else {
        //                 sum -= one;
        //             }
        //         }

        //         if (sum % 3 == 2) {
        //             int two = Mtwo.top();
        //             if (Mone.size() == 2) {
        //                 int one1 = Mone.top();
        //                 Mone.pop();
        //                 int one2 = Mone.top();
        //                 cout << one1 << " " << one2;
        //                 sum = max(sum - two, sum - one1 - one2);
        //             } else {
        //                 sum -= two;
        //             }
        //         }
        //     }
        //     return sum;
        // vector<int> one, two;
        // int sum = 0;
        // for (auto& e : nums) {
        //     if (e % 3 == 1) {
        //         one.push_back(e);
        //     }
        //     if (e % 3 == 2) {
        //         two.push_back(e);
        //     }
        //     sum += e;
        // }
        
        // sort(one.begin(), one.end());
        // sort(two.begin(), two.end());

        // while (sum % 3 != 0) {
        //     if (sum % 3 == 1) {
        //         // 拿出最小的1，以及两个2
        //         int one1 = one.front();
        //         if (two.size() >= 2) {
        //             int two1 = two.front();
        //             int two2 = two[1];
        //             cout << "two: ";
        //             cout << two1 << " " << two2;                    
        //             sum = max(sum - one1, sum - two1 - two2);
        //         } else {
        //             sum -= one1;
        //         }
        //     }

        //     if (sum % 3 == 2) {
        //         int two1 = two.front();
        //         if (one.size() == 2) {
        //             int one1 = one.front();
        //             int one2 = one[1];
        //             cout << "one: ";
        //             cout << one1 << " " << one2;

        //             sum = max(sum - two1, sum - one1 - one2);
        //         } else {
        //             sum -= two1;
        //         }
        //     }
        // }

        // return sum;
        const int INF = 0x3f3f3f3f;
        int sum = 0, x1, x2, y1, y2;
        x1 = x2 = y1 = y2 =INF;
        for (auto e : nums) {
            sum += e;
            if (e % 3 == 1) {
                if (e < x1) x2 = x1, x1 = e;
                else if (e < x2) x2 = e;
            } 
            if (e % 3 == 2) {
                if (e < y1) y2 = y1, y1 = e;
                else if (e < y2) y2 = e;
            }
        } 
        if (sum % 3 == 2) return max(sum - y1, sum - x1 - x2);
        else if (sum % 3 == 1) return max(sum - x1, sum - y1 - y2);
        else return sum;
    }
};

class Solution06 {
    unordered_map<int, int> hash;
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int len = barcodes.size();
        vector<int> ret(len);
        sort(barcodes.begin(), barcodes.end());
        for (auto e : barcodes)
            hash[e]++;
        int mostnum = 0, large = INT_MIN;
        for (auto& [x, y] : hash) {
            if (y > large) {
                large = y;
                mostnum = x;
            }
        }
        int index = 0;
        for (int i = 0; i < len; i++) {
            if (barcodes[i] == mostnum) {
                index = i;
                break;
            }
        }

        // 从该位置出发
        for (int i = 0; i < len; i += 2) {
            ret[i] = barcodes[index];
            index = (index + 1) % len;
        }

        for (int i = 1; i < len; i += 2) {
            ret[i] = barcodes[index];
            index = (index + 1) % len;
        }

        return ret;
    }
};

class Solution {
    unordered_map<char, int> hash;

public:
    string reorganizeString(string s) {
        string ret;
        int len = s.size();
        ret.resize(len);
        char mostch;
        int mostnum = 0;
        for (char ch : s) {
            hash[ch]++;
            if (mostnum < hash[ch]) {
                mostch = ch;
                mostnum = hash[ch];
            }
        }

        // if (mostnum > (len + 1) / 2)
        //     return "";

        int index = 0;
        for (int i = 0; i < mostnum; i++) {
            ret[index] = mostch;
            index += 2;
            if (index >= len)
                index = 1;
        }
        hash.erase(mostch);

        for (auto& [x, y] : hash) {
            for (int i = 0; i < y; i++) {
                if (index >= len)
                    index = 1;
                ret[index] = x;
                index += 2;
            }
        }

        for (int i = 0; i < len - 1; i++)
            if (ret[i] == ret[i + 1])
                return "";

        return ret;
    }
};

int main() {

    return 0;
}